import java.util.Arrays;

/**
 * @Author MRC
 * @Description 指针交换法实现的快速排序
 * @Date 10:45 2020/5/26
 **/
public class QuickSort2 {

    public static void main(String[] args) {
        int[] array = {4, 7, 6, 5, 3, 2, 9, 1};
        sort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    private static void sort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivotIndex = partition(array, start, end);
        sort(array, start, pivotIndex - 1);
        sort(array, pivotIndex + 1, end);
    }

    private static int partition(int[] array, int start, int end) {

        //取首位为基准元素。//也是坑的位置
        int pivotIndex = start;
        //基准元素的值
        int pivot = array[pivotIndex];
        //左边指针
        int left = start;
        //右边指针
        int right = end;

        while (right != left) {
            /**
             * 操作右指针
             */
            while (right > left && pivot < array[right]) {
                right--;
            }
            /**
             * 操作左指针
             */
            while (right > left && pivot >= array[left]) {
                left++;
            }
            /**
             * 交换元素
             */
            if (right > left) {
                int item = array[right];
                array[right] = array[left];
                array[left] = item;
            }
        }

        /**
         * 交换指针位置和基准元素
         */
        array[pivotIndex] = array[left];
        array[left] = pivot;
        return left;
    }
}
